#ifndef _DISAMBIGUATION_
#define _DISAMBIGUATION_
#include "SequenceGraph.h"
#include "Global.h"
#include "FibHeap.h"
#include <map>
#include <vector>
#include <set>
#include <deque>
#include <fstream>
using namespace std;

class Disambiguation
{
private:
	class PathNode: public AbstractHeapNode {
	public:
		PathNode( GID_T seqVID, PathNode* pred = NULL): seqVertexID(seqVID), dist(0), parent(pred) {}
		GID_T seqVertexID;
		int dist;
		PathNode* parent;
		inline static int cmp_func(void* node1, void* node2) {
			assert(node1 != NULL && node2 != NULL);
			PathNode* ele1 = (PathNode*) node1;
			PathNode* ele2 = (PathNode*) node2;
			if (ele1 == ele2 || ele1->dist == ele2->dist) {
				return 0;
			} else if (ele1->dist > ele2->dist) {
				return 1;
			} else {
				return -1;
			}
		}
	};

	class CandidateNode: public AbstractHeapNode {
	public:
		CandidateNode( GID_T seqVID ): AbstractHeapNode(), seqVertexID(seqVID), dist(0) {}
		// default copy constructor is ok.
		GID_T seqVertexID;
		int dist;
		vector<CandidateNode*> parents;
		static int cmp_func(void* node1, void* node2)  {
			assert(node1 != NULL && node2 != NULL);
			CandidateNode* ele1 = (CandidateNode*) node1;
			CandidateNode* ele2 = (CandidateNode*) node2;
			if (ele1 == ele2 || ele1->dist == ele2->dist) {
				return 0;
			} else if (ele1->dist > ele2->dist) {
				return 1;
			} else {
				return -1;
			}
		}
	};

	struct ReadInSequence {
		GID_T seqVertexID;
		int offset;
		int confidence;
		ReadInSequence(GID_T seqVid = 0, int off = 0, int conf = 0):
			seqVertexID(seqVid), offset(off), confidence(conf) {}
	};

	struct PairedSequenceInfo {
		GID_T seqVertexID;
		int coordinate;
		int confidence;
		PairedSequenceInfo(GID_T seqVid = 0, int coord = 0, int conf = 0):
		seqVertexID(seqVid), coordinate(coord), confidence(conf) {}
	} NoPairedSequenceInfo;

	fstream fcontig;
	ofstream fstatis;
	
	SequenceGraph* m_seqGraph;
	int m_insert;
	int m_stddev;
	int m_maxSeedCoverage;
	GCOUNT_T m_numOfReads;
	int m_readLength;
	vector<GID_T> m_seeds;
	ReadInSequence* m_readInSequence; //< [readID] = sequenceID, offset
	int m_pairSupport;	//< how many mate pairs are enough to support two long pair nodes
	int m_pairKSupport;	//< m_pairSupport * (K - 1)
	int m_contigsCount;

	int m_longest;
	int m_numOfContigs;

	unsigned char* m_queued; // if a seed is ever queued
	inline bool isQueued(GID_T id) { id = abs(id); return (m_queued[id >> 3] >> (id % 8)) & 1; }
	inline void setQueued(GID_T id) { id = abs(id); m_queued[id >> 3] |= (1 << (id % 8)); }
	unsigned char* m_seed; // if a vertex is seed
	inline bool isSeed(GID_T id) { id = abs(id); return (m_seed[id >> 3] >> (id % 8)) & 1; }
	inline void setSeed(GID_T id) { id = abs(id); m_seed[id >> 3] |= (1 << (id % 8)); }
	unsigned char* m_visited; // used in shortest path paving
	inline void clearVisited() {	memset(m_visited, 0, ((m_seqGraph->maxVertexID()) >> 3) + 1); }
	inline bool isVisited(GID_T id) { id = abs(id); return (m_visited[id >> 3] >> (id % 8)) & 1; }
	inline void setVisited(GID_T id) { id = abs(id); m_visited[id >> 3] |= (1 << (id % 8)); }
	unsigned char* m_outputed; // if a vertex has outputed
	inline bool isOutputed(GID_T id) { id = abs(id); return (m_outputed[id >> 3] >> (id % 8)) & 1; }
	inline void setOutputed(GID_T id) {  id = abs(id); m_outputed[id >> 3] |= (1 << (id % 8)); }

	void cleanAllocated(vector<AbstractHeapNode*>& allocated);

	/**
	 * sort by sizes of sequence nodes
	 */	
	struct size_compare {	
		size_compare(SequenceGraph* seqGraph): sequenceGraph(seqGraph) {}
		SequenceGraph* sequenceGraph;
		bool operator()( const GID_T id1, const GID_T id2 ) const
		{
			return sequenceGraph->getVertexByID(id1)->size() > sequenceGraph->getVertexByID(id2)->size();
		}
	};

	/**
	 * detect non-repeating nodes
	 */
	void seeding();

	/**
	 *	 Build virtual coordinates to form a basic series of nodes that buttress a contig.
	 * @param skeleton the coordinates with nodes
	 * @param init_seed the initial node that has coordinate 0.
	 */
	void buildSkeleton(map<int, GID_T>& skeleton, GID_T init_seed);

	/**
	 *
	 * @param startNodeID 
	 * @param endNodeID 
	 * @param meanLength 
	 * @param bridge pavedPath
	 */
	void pave(GID_T startNodeID, GID_T endNodeID, int meanLength, deque<GID_T>& bridge);

	/**
	 *
	 * @param readId readId read id in current vertex
	 * @param offset read offset in current vertex
	 * @param coordinate coordinate of current vertex
	 * @return paired vertex id, coordinate of paired read and confidence
	 */
	PairedSequenceInfo getPairedSequence(GID_T readId, int offset, int coordinate);

	/**
	 * Generate candidates that is possible to pave the gap between start and end
	 * @param candidates 
	 * @param startNodeID 
	 * @param endNodeID 
	 * @param maxLength 
	 */
	void generateCandidates(set<GID_T>& candidates, GID_T startNodeID, GID_T endNodeID, int maxLength);

	/**
	 * Find nodes that just fill the gap between two nodes by brute force
	 * @param startNodeID 
	 * @param endNodeID 
	 * @param meanLength 
	 * @param bridge nodes including start and end that pave the gap between them
	 * @param candidates candidate nodes will be used in this function
	 */
	void bruteForcePave(GID_T startNodeID, GID_T endNodeID, int meanLength, deque<GID_T>& bridge, set<GID_T>& candidates);

	void tryExtend(SequenceVertex* midVertex, deque<GID_T>& contig);

public:
	Disambiguation(SequenceGraph* seqGraph, ReadInputFacts& readSet,
		int pairSupport, int maxSeedCoverage, const char* outFile, const char* statisFile);
	~Disambiguation();
	void allContigs();
	GINT32 getLongestLength() { return m_longest; }
	GINT32 getNumOfContigs() { return m_numOfContigs; }
};

#endif